using System.Collections.Generic;

namespace Test.ConsoleProgram.Algorithm.Solution
{
    [TestDescription("算法: 0145. 二叉树的后序遍历")]
    public class No0145_PostorderTraversal : AbsBaseTestItem
    {
        /*
        给定一个二叉树，返回它的 后序 遍历。
        进阶: 递归算法很简单，你可以通过迭代算法完成吗？
        */

        public class TreeNode
        {
            public int val;
            public TreeNode left;
            public TreeNode right;
            public TreeNode(int val = 0, TreeNode left = null, TreeNode right = null)
            {
                this.val = val;
                this.left = left;
                this.right = right;
            }
        }

        public override void OnTest()
        {
            Assert.TestExe(PostorderTraversal,
                new TreeNode(1)
                {
                    right = new TreeNode(2)
                    {
                        left = new TreeNode(3),
                    }
                },
                new int[] { 3, 2, 1 });
        }

        public IList<int> PostorderTraversal(TreeNode root)
        {
            if (root == null) return new int[] { };
            var list = new List<int>();
            list.AddRange(PostorderTraversal(root.left));
            list.AddRange(PostorderTraversal(root.right));
            list.Add(root.val);
            return list;
        }
    }
}
